Memory reclamation is a key issue for computer systems. It is often difficult to implement memory reclamation correctly and efficiently. As computer hardware moves to provide increasing amounts of memory and increasing numbers of processors, memory reclamation is becoming an even greater concern, given the large amount of resources to be managed and the higher degree of concurrency in modern processor architectures.
Conventionally, memory reclamation is performed “manually” by the programmer, who explicitly specifies a memory release action in the program code. This approach leads to significant development cost as well as complex and difficult-to-diagnose errors.
In response, automatic reclamation techniques are developed. Some automatic reclamation techniques are based on scanning memory for unreferenced objects. One common approach is referred to as a tracing or “mark and sweep” approach. The technique becomes increasingly expensive as the size of main memory grows because the running time for performing a “mark and sweep” action increases, creating more interference with application progress, and often causing long pauses. This approach also makes the time to reclaim memory unpredictable, making it difficult to determine the amount of physical memory required to satisfy application requirements.
Alternatively, automatic reclamation may be based on maintaining a reference count per object and freeing the object when the reference count goes to zero, which indicates that there are no other references to this object. This approach, however, cannot reclaim memory when there is a cycle in the references. For example if object A points to object B and object B also points to object A, then A has a non-zero reference count independent of whether there are any other references to A; similarly, B also has a non-zero reference count. Thus, neither A nor B is ever reclaimed even though neither is reachable from the rest of the application. Some improved techniques combine mark and sweep with reference counting; however, these techniques tend to be inefficient and complex.